//组合总和 力扣39
//回溯算法 递推层数不确定 startsindex控制在相同集合内每一层循环遍历的范围
class Solution {
public:
	vector<int> path;
	vector<vector<int>> ans;
	int sum = 0;
	void backtracking(vector<int> candidates,int target,int startindex)
	{
		if(sum > target) return;
		if(sum == target) 
		{
			ans.push_back(path);
			return;
		}
		for(int i = startindex; i < candidates.size(); i++)
		{
			path.push_back(candidates[i]);
			sum += candidates[i];
			backtracking(candidates,target,i);
			path.pop_back();
			sum -= candidates[i];
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		backtracking(candidates,target,0);
		return ans;
	}
};
